Neoterics is a simple Artificial Life program I have developed to educate myself in the basic principles of the field. It is an ongoing project, as I intend to add to each version additional capabilities as I find the time.
The current implementation of Neoterics (1.0b) consists of a toroidal plane of discrete locations, each of which contains a level of available food energy (plants). On this pseudo-world resides a collection of Artificial Neural Networks (ANNs) that have behaviors based upon a created or inherited genome. The creatures have the ability to sense the surroundings, and act according to the ANN output using one of five actions: Advance, Turn Left, Turn Right, Eat, or Breed.
The Neoterics world is a closed system. The amount of energy available is a fixed quantity. Therefore, the simulation can be viewed as the ANN's evolving to gather and transmit to their offspring more energy than the other competitors.
The Landscape:
The Neoterics world is a square lattice of size 2^N, where N is an integer between 4 and 12, inclusive. The edges are "wrapped" to touch, forming a torus (doughnut) shaped geometry, so that edge effects do not develop. The size restriction to powers of 2 is for computer optimization, and is one of the reasons for the fast simulation rates achieved by the program.
On each discrete location is a certain level of available food, or "plants". The level of the food is kept in a unsigned character array, giving levels of 0-255. At the onset of the simulation a user-specified number of these locations are set to a level of 128. This and the initial creature set define the energy capacity of the system.
At the end of each simulation step there is an energy use accumulator that contains the amount of the energy used in the actions of the creatures that has not been stored in their bodies. This energy is distributed randomly, in packets of size 128, to the terrain. No location is overflowed, and any remaining amount (after the packets of size 128 are distributed) is also given to a random location.
The level of energy available at a location determines its color. Green is used to denote energy, black indicating none, bright green indicating 255. To see smaller differences in the energy level the monitor should be set for 24-bit color. 256 color displays show approximately 4 shades of green, but it has not been determined what the energy level cut-off points for each shade is.
The Creatures:
Each creature in the initial set is randomly placed on the landscape and given an initial random direction. Possible directions for a creature are the four cardinal directions (N,W,S,E). The initial energy level (for creatures created at simulation startup) is 1000. The genome is initialized using the C "rand" function, and so should give an approximate 50% bit level encoding.
Each time step the program iterates through all currently alive creatures (death is explained below) and processes the ANN for each creature, performs the creature's action, and ages the creature. Processing of the ANN is described in the following section. Creature actions and aging are discussed here.
The creature can perform one of five actions each timestep; Move Forward, Turn Left, Turn Right, Eat, and Breed. Turning modifies the creatures direction without changing its location, and consumes one energy unit. Moving forward changes the location according to the creature's current direction (with wrap-around on terrain edges), and consumes 2 energy units. All expended energy returns to the terrain (food) at the end of the time-step.
The Eat action causes the creature to attempt to extract food from the current location. The creature will remove up to 64 units of energy if that much is available. One quarter of the removed food (rounded down to an integer value) goes into the energy "pot" to be distributed at the end of the time-step. This is to model (crudely) the inefficiency of metabolism. The remaining energy goes to the creature's internal energy store, up to a maximum of 2047. Any overflow will be removed from the creature and put into the energy "pot". Note that the initial food amounts (and the redistribution amounts) of 128 allow two Eat actions before the food at that location is exhausted.
The Breed action causes the creature to attempt to reproduce. For a description of reproduction, see the section below.
Each creature is given an age of 0 at birth, and the age count increases by one for every time-step that it is alive. When this count is greater than the age factor (initially set to 512, but always a power of 2 for computational purposes) the energy level of the creature is decreased by an amount equal to the integer portion of the age divided by the system age factor. As always, this energy is put into the "pot" for redistribution.
If a creature's energy store gets below a threshold, 5 in this implementation, then the creature dies. Any remaining energy is added to the distribution "pot", the creature is removed from the simulation queue, and it's graphic is removed from the over-head display. In simulations with the "Minimum Population" flag set on, if less than the specified number of creatures remain, a new one will be created, either from scratch or from a mutated clone of one of the survivors (depending on options set for the run) The energy given to an "underflow" creature is removed from the energy "pot" to keep the energy balance for the system.
Reproduction:
When a creature attempts to reproduce, it first tries sexual reproduction, and then failing that, asexual progeny are generated. To limit the population (and stimulate evolution toward better energy retrieval and management) the energy required is computed as 1000 + 1050 / (Maximum Creatures - Number Of Creatures + 1). Thus, as the population approaches the maximum, more energy is needed for reproduction. Each offspring is given 800 energy units. and the parent or parents are allocated 100 for continued survival (No give-everything-to-reproduce strategies). All energy above the 800 for the offspring and 100 spare for the parent(s) goes into the energy "pot" for redistribution at the end of the time-step. If the creature does not have the required energy for reproduction, 5 energy units are removed for metabolism that time step (and put into the energy "pot") and no other action is performed for that creature.
For sexual reproduction the "father" searches for another creature (the "mother") at the same location with an action flag of "breed". If none is found asexual reproduction is tried. If a mother is found, each parent's energy level is compared to half of the needed energy. If both parents have enough an offspring is created and is given the 800 energy units, a random initial direction, the parent's location, and a crossover of the parent's genomes modified by the mutation operator. The crossover and mutation operation is performed with the user-specified bit probability (default = 0.002, and 0.008 respectively). The parents energy levels are then reduced by half the needed energy minus the 50 units spare. If either parent does not have the energy for reproduction, both have 5 units transferred to the "pot", and the breed flags turned off for the time-step.
For asexual reproduction the single parent creature needs to have all the energy to create the creature, continue existence, and cover the inefficiency energy requirements before an offspring can be created. This means that the creature needs at least 1000 energy units to successfully reproduce asexually. If the condition is met the offspring is created and is given the 800 energy units, a random initial direction, the parent's location, and a copy of the parent's genome modified by the mutation operator. The parent's energy level is then reduced by the needed energy minus the 100 units spare.
The Artificial Neural Network:
Each creature's genome defines the sensors, weights and thresholds of a neural network that is used to determine the actions of the creature at each time step. The network consists of three layers of neurons; the input layer, the "hidden" layer, and the output layer; each with different properties.
The input layer is used for sensor normalization and distribution only. Each of the eight sensors have an input neuron associated with it. The eight sensors are determined by the genome to be either a food or creature sensor at a given relative position, or an internal sensor for energy, age, location, direction, last action, or a random value. Food level values are just the integer food level at the specified location. Creature sensors are either off or on for the specified location, with values of 0 and 255 respectively. The location for each food or creature sensor is one of 49 locations consisting of a 7x7 grid relative to the creature in the center facing in the -y axis direction, with screen coordinate offsets used (see diagram below).
1000002
0000000
000^000
0000000
3000004
where ^ - creature relative location (0,0)
1 - relative location (-3,-3)
2 - relative location (3,-3)
3 - relative location (-3,3)
4 - relative location (3,3)
The possible internal sensors include energy level for the creature, which is divided by four (and rounded down) for the input; location, which is normalized to a 0-255 range based on the terrain size parameter; direction, which is mapped as N=0, E=64, S=128, and W=192; age, which is divided by the age factor (and rounded down); last action (an integer enumerated value); and a random number between 0 and 255.
Each of the 12 "hidden" neurons take an input from each of the sensor neurons, multiplies it by a signed 8-bit weight constant from the genome and totals the product. If the result is greater than the threshold for the neuron, which is an unsigned 8-bit unsigned number that is multiplied by four before the comparison (0-1020 range), then the neuron is considered "activated", otherwise it is "inhibited".
The output, or action, layer of the neural network sums the weights determined by the genome for the connections between it and each of the "activated" hidden layer neurons. After each neuron has calculated this sum, the action neuron with the highest value determines the creature's next action. This is the "winner-take-all" method. Since there are 5 actions the creature can perform, there are 5 output layer neurons.
The network is fully connected, without recursion, making the size of the genome 1408 bits, or 176 bytes. This results from the following equation:
The genome is kept in a sequential array of bytes that can be manipulated using normal genetic operators, mutation and crossover. Initialization of the genome is done using a normal C random number generator, and so should average to a 50% bit set rate for the initial generation.
During asexual reproduction, the parents genome is copied into the genome for the offspring. This genome is then mutated using a bitwise probability specified by the user. If the probability is less than 1/2^31, the mutation operation is not performed. For computational speed, an approximate normalized distribution is formed by adding 16 random numbers, then dividing by 16 times the average of the random number generator. This value is multiplied by the mutation bit rate times the number of bits in the genome. This value is rounded to give the number of bits that are to be mutated in the genome. Random byte and bit indexes are then chosen for each bit to be mutated, and the value of the indicated bit is swapped. Note that there is nothing preventing the same bit from being mutated twice, effectively resulting in no change to the genome.
Sexual reproduction starts with genetic crossover. If the crossover probability is less than 1/2^31, no crossover will be performed. If it equals 1.0, exactly one crossover point will be used. Values other than these result in a stochastic determination of the number of crossover sites. The number of crossover points in this case is determined similar to the mutation calculation; an approximate distribution is formed by adding 16 random numbers and dividing by the expected mean which is multiplied by the number of genome bits times the crossover probability, which is then rounded. If the number of crossover sites is 0, then no crossover is performed. Otherwise, for each crossover site a random location along the genome is chosen for the source of the genetic material for the copy to be toggled between the father and the mother. The source initially starts with the father. For an example, consider the 2-site crossover below, where each letter represents a bit in the genome:
Father ....FFFFFFFFFFF....
Mother ....MMMMMMMMMMM....
Child ....FFFMMMMFFFF....
After crossover (if any) the mutation operation is performed on the offspring's genome.
PROGRAM OPERATION:
The Neoterics program is a fairly standard Mac application with windows and menus. The main window is the overhead view, with two floater windows for simulation status and creature information:
Menus:
Each of the Neoteric program specific menu options are discussed here:
Set Parameters:
This menu command invokes the Initial Parameters dialog box for editing of the simulation constants. The menu command is only available when no simulation is active. See below for a description of the used of this dialog box.
Run:
This menu command starts the simulation, using the Initial Parameters (see above). It automatically activates the "Overhead View" window and the "Status" floater window. After the initial terrain is generated and the initial creature set produced, the simulation proceeds at full speed. This command is only available when no simulation is active
Pause/Resume:
This menu command toggles the simulation between the paused state and the full-out run mode. It is only available when a simulation is active.
Single Step:
This menu command advances the simulation one time step. This command is only available when an active simulation is paused.
Leave Trails/Remove Trails:
This menu command toggles the simulation between the leave-trails and no-trails state. When the simulation is leaving trails, the graphic at a creature's previous position is not erased when it moves, leaving a trail of it's motion. When switched to the no-trails state, the overhead-view is redrawn to remove the trails, and movement graphic erasures are performed. The simulation starts in the no-trails state. This command is only available when a simulation is active or paused.
Scale:
This sub-menu allows the user to change the graphics scale on the fly. The overhead view starts at the x2 scale, which gives each creature and terrain location a 2x2 rectangle on the graphic. At scale x1, each creature and location is a point. At higher scales, the location is a rectangle of the given size and the creatures are triangles which point towards the creatures current direction (except at the x32 scale, where the creatures are drawn using color icons!).
The Initial Parameters Dialog:
When the "Set Parameters" menu command is invoked this dialog box appears. Using it the user can set the parameters for the simulation. Each control on the dialog box is outlined here:
Terrain Size - This pop-up menu sets the dimensions of the terrain size. Each selection gives a power of 2 between 64 and 16384 for both sides of the square terrain. The number of discreet locations is obviously the square of this selection.
Initial Number of Food Locations - This parameter sets the number of food locations that are initialized with food at the beginning of the simulation. The initial settings for the locations is 128 units, giving 128 * number-of-locations + 1000 * number-of-creatures total energy for the system. This value cannot be negative and must be less than or equal to the square of the Terrain Size parameter.
Probability of Crossover - This is the bitwise probability of crossover. If 0.0, no crossover will be performed. If 1.0, crossover will be performed during sexual reproduction with exactly one crossover site. Numbers outside of the 0.0-1.0 range are invalid, and other numbers between that range cause a stochastic determination of the number of crossover sites, based on the bit size of the genome multiplied by this constant.
Probability of Mutation - This is the bitwise probability of mutation. As the last step of all reproductions, both sexual and asexual, the offspring's genome is mutated with the number of bits swapped stochastically determined based on this parameter times the bit size of the genome. Valid values for this parameter are between 0.0 and 1.0, inclusive. A value of 0.0 turns off the mutation operator.
Maximum Number of Creatures - This value is the maximum number of creatures that the simulation will allow at one time. Other constraints (energy) may limit the number of creatures that actually appear at any given moment to be less than this value.
Initial Number of Creatures - This is the number of creatures created at the beginning of the simulation. Each of these creatures is given 1000 energy units, which gives the energy total for the system equal to the value described in the Initial Food Locations parameter. This value must be greater than 0 and less than or equal to the Maximum Number of Creatures.
Keep Minimum Population Flag - This flag determines whether new creatures will be created if the population drops below a specified threshold during the simulation. If the flag is off and the population drops to 0 the simulation is stopped. If the flag is on and the population drops below the threshold a new creature is created and placed in the simulation. New creatures are given an energy of 1000 units, but that energy is removed from the energy "pot" so as to keep the total energy in the system remains constant. Note that the energy "pot" can go negative for a short time if a new creature is being created, creating a temporary spike in total system energy if this occurs. The created creature is given a random location and direction, and is marked as created by "Underflow".
Minimum Number of Creatures - This is the threshold for new creature creation. This value is only used if the Keep Minimum Population flag is on. Valid entries for this number are between 1 and the Maximum Number of Creatures, inclusive.
Use Survivor for Clone Flag - This flag determines the genome source for creatures created to keep a minimum population. If it is not set, the creature gets a randomly initialized genome. If the checkbox is set on the creatures genome will be a mutated version of one of the remaining creatures.
Age Factor - This pop-up menu sets the age factor for the creature. At the end of each time step each creature's age is divided by this value (the result being rounded down) and that amount of energy is removed from the creature and returned to the system, effectively given an age limit to each member of the population.
Give Head Start Flag - This option gives the initial set of creatures an advantage towards surviving by setting two of their sensors to food values at the current and immediately forward locations (see the discussion on sensors above) and doing a partial back-propagation learning phase for eating when on food and moving forward when food ahead, all before the simulation starts. This option was added after having several attempts at getting a viable run failed after over 20 starts! With this option on a viable run now occurs approximately 1 in every three attempts.
The Overhead View:
The Overhead view window shows the terrain and creatures in real-time. The window can be moved and resized as needed. The draw scale can be set using menu commands (see above). If the scale is large enough so that the entire terrain cannot be seen within the window, scroll bars will become active that will allow the user to pan to different areas. Changing the scale of the Overhead View will cause the scrolled region to jump to the upper-left hand corner of the terrain.
Clicking on the close box of the Overhead View window, or using the Close command from the file menu will stop the current simulation. Once it is stopped in this manner it CANNOT be restarted, so be careful where you click!
Clicking on a creature graphic within the overhead display will bring up the Creature Information floater window, or if it is already active it will change the information to that for the newly selected creature. For a description of the fields on this window see the description below.
The Status Window:
The Status window shows the current simulation status for time in steps, the current creature population, and the number of births. The birth field has two numbers. The first is the number of asexual reproductions, and the second the number of sexual reproductions. The Status window is updated every 5 time steps. It is a floater window that can be moved if desired, although it is always active as long as a simulation is running.
The Creature Information Window:
When a creature is selected in the Overhead View window, the Creature Information window is activated. This window shows all the pertinent information for the selected creature. The update rate for the window can be selected to be 1, 2, 5, 25, or 100 time-steps using the radio buttons at the top of the window.
The window shows the creature ID, location and direction (coordinates and cardinal compass point), its age, energy level, parentage (by production type and parent ID's), and the genome. The genome is decoded into a scrolling list to show the sensor connections and the ANN weights and thresholds. Since the parentage and the genome does not change for a creature, these fields are only updated when a new creature is selected for display. If the creature being viewed dies, the fields are blanked until another creature is born using the same memory location, at which time that creature's information will be shown.
Clicking in the close box of the Creature Information window will close the window without affecting any other part of the simulation. The simulation does run faster without the Creature information window active.
Execution Notes:
The Neoterics program requires a 68020 or better processor, and a 68881 compatible floating-point coprocessor. Memory requirements are related to the simulation, but 1-2 Megabytes should be sufficient for all runs. The program will run in the background, and should not effect other programs, other than in performance. At the time of this writing the program had not been tried on a Power-Macintosh, and so it is unknown whether the 680LC40 emulation would run it appropriately. The program was written using MetroWerks CodeWarrior and the PowerPlant application framework.
While the simulation is fairly fast, there are things that can be done to speed it up. The graphic redraws are expensive, so set the overhead view scale high (x32) and keep the window small so redraws only have to occur on a small portion of the terrain and population. If not using the Creature Information window, dismiss it so it is not being updated. Leave disks in all slots (floppy, CD, etc.) so the operating system is not checking for disk insertion events. The colors depths for the window redraws are 24 bit, so set the monitor color depth as high as possible to limit color palette search times on the redraw.
The following speeds have been observed on 680x0 based machines with the default window size and the drawing scale at x32:
Mac IIx - 350 creature-updates/sec
Quadra 650 - 1330 creature-updates/sec
Command Key Summary:
I - Set Initial Parameters
R - Run Simulation
; - Pause/Resume Simulation
1 - Single-Step the Simulation
L - Leave/Remove Trails
Q - Quit Program
Comments and questions will be gladly excepted. Send them to:
